package 力扣题库;

import 剑指offer.ListNode;

public class p109有序链表转换二叉搜索树 {
    public TreeNode sortedListToBST(ListNode head) {
        //观察可能的树，发现我们选择链表中间的数作为根节点，分给左右子树的节点个数相同，或只相差1，保证树的平衡
        //找出链表中间节点作为根节点的值，使用 快慢指针
        // 链表长度是奇数，则根节点的选择是唯一的
        // 链表长度是偶数，使用 快慢指针的方法找中间节点，则对应中间位置右边的数字作为根节点
        //中位数：如果链表中的元素个数为奇数，那么唯一的中间值为中位数；如果元素个数为偶数，那么唯二的中间值都可以作为中位数，而不是常规定义中二者的平均值。

        return buildTree(head,null);

    }

    private TreeNode buildTree(ListNode left, ListNode right) {
        if (left==right) {
            return null;
        }

        ListNode mid=findMid(left,right);
        TreeNode root=new TreeNode(mid.val);
        root.left=buildTree(left,mid);
        root.right=buildTree(mid.next,right);
        return root;
    }

    private ListNode findMid(ListNode left,ListNode right) {
        //使用 快慢指针的方法找中间节点，则对应中间位置右边的数字作为根节点
        ListNode fast=left;
        ListNode slow=left;

        while (fast!=right && fast.next!=right) {
            //奇数个 fast==right结束循环
            //偶数个 fast.next==right结束循环
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;//返回中位数链表节点
    }
}
